package com.zang.tree;

import java.util.*;

/**
 *
 * N叉树的层序遍历
 *
 * @author ZVerify
 * @since 2022/10/23 15:28
 * @see <a href="https://leetcode.cn/problems/n-ary-tree-level-order-traversal/">...</a>
 **/
public class N叉树的层序遍历 {

    public List<List<Integer>> levelOrder(Node root) {

        if(root == null) return Collections.emptyList();

        if (root.children.isEmpty()) return Collections.singletonList(Collections.singletonList(root.val));

        List<List<Integer>> list = new ArrayList<>();

        Deque<Node> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()) {

            ArrayList<Integer> arrayList = new ArrayList<>();
            int size = deque.size();
            for (int i =0;i<size;i++){
                Node poll = deque.poll();
                arrayList.add(poll.val);
                if (poll.children.isEmpty()) continue;
                for (Node child : poll.children) {
                    deque.addLast(child);
                }
            }
            list.add(arrayList);

        }
        return list;
    }
}
